package com.leetcode.partition8;

import java.util.*;

/**
 * @author `RKC`
 * @date 2021/10/8 18:51
 */
public class LC721账户合并 {

    public static List<List<String>> accountsMerge(List<List<String>> accounts) {
        return unionFind(accounts);
    }

    public static void main(String[] args) {
        List<List<String>> accounts = new ArrayList<>();
        // [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],
        // ["Mary","mary@mail.com"],
        // ["John","johnnybravo@mail.com"]]
        accounts.add(Arrays.asList("John", "johnsmith@mail.com", "john_newyork@mail.com"));
        accounts.add(Arrays.asList("John", "johnsmith@mail.com", "john00@mail.com"));
        accounts.add(Arrays.asList("Mary", "mary@mail.com"));
        accounts.add(Arrays.asList("John", "johnnybravo@mail.com"));
        System.out.println(accountsMerge(accounts));
    }

    private static List<List<String>> unionFind(List<List<String>> accounts) {
        List<List<String>> answers = new ArrayList<>();
        //key为邮箱，value为账户索引
        Map<String, Integer> emailToId = new HashMap<>();
        int[] ancestors = new int[accounts.size()];
        //并查集初始化
        for (int i = 0; i < accounts.size(); i++) ancestors[i] = i;
        for (int i = 0; i < accounts.size(); i++) {
            int size = accounts.get(i).size();
            for (int j = 1; j < size; j++) {
                String email = accounts.get(i).get(j);
                //当前邮箱没有出现过
                if (!emailToId.containsKey(email)) {
                    emailToId.put(email, i);
                    continue;
                }
                //当前邮箱已经出现过，代表两个用户是同一个
                union(ancestors, i, emailToId.get(email));
            }
        }
        //此时同一个用户的所有邮箱都已经属于同一个连通域，但是就算在同一个连通域，不同的邮箱还是有可能会对应不同的id
        //<账户id, 邮箱列表>，因为名称可能会出现相同的，因此只能用账户id来区别不同的用户
        Map<Integer, List<String>> idToEmails = new HashMap<>();
        //将同一个连通域内的邮箱对应到一个id
        for (Map.Entry<String, Integer> entry : emailToId.entrySet()) {
            int ancestorId = find(ancestors, entry.getValue());
            if (idToEmails.containsKey(ancestorId)) {
                idToEmails.get(ancestorId).add(entry.getKey());
            } else {
                List<String> emails = new ArrayList<>();
                emails.add(entry.getKey());
                idToEmails.put(ancestorId, emails);
            }
        }
        //将用户名和邮箱对应
        for (Map.Entry<Integer, List<String>> entry : idToEmails.entrySet()) {
            String account = accounts.get(entry.getKey()).get(0);
            List<String> ans = new ArrayList<>();
            ans.add(account);
            Collections.sort(entry.getValue());
            ans.addAll(entry.getValue());
            answers.add(ans);
        }
        return answers;
    }

    private static int find(int[] ancestors, int x) {
        //压缩方式，直接指向根结点，避免多次进行递归查询
        if (x != ancestors[x]) ancestors[x] = find(ancestors, ancestors[x]);
        return ancestors[x];
    }

    private static void union(int[] ancestors, int x, int y) {
        int parentX = find(ancestors, x), parentY = find(ancestors, y);
        ancestors[parentY] = parentX;
    }
}
